Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Complexity analysis of functional query answering on big data
Wenli WU, Guohua LIU, Junbao ZHANG
Journal of Computer Applications    2020, 40 (2): 416-419.   DOI: 10.11772/j.issn.1001-9081.2019091618
Abstract401)   HTML0)    PDF (436KB)(235)       Save

Functional query is an important operation in big data application, and the problem of query answering has always been the core problem in database theory. In order to analyze the complexity of the functional query answering problem on big data, firstly, the functional query language was reduced to a known decidable language by using mapping reduction method, which proves the computability of the functional query answering problem. Secondly, first-order language was used to describe the functional query, and the plexity of the first-order language was analyzed. On this basis, the NC-factor reduction method was used to reduce the functional query class to the known Π Τ Q -complete class. It is proved that functional query answering problem can be solved in NC time after PTIME (Polynomial TIME) preprocessing. It can be conducted that the functional query answering problem can be handled on big data.

Table and Figures | Reference | Related Articles | Metrics